import numpy as np
from typing import Dict, List, Tuple

class GraphUtils:
    @staticmethod
    def floyd_warshall(adj_matrix: np.ndarray) -> Tuple[np.ndarray, np.ndarray]:
        """
        执行Floyd-Warshall算法，返回最短距离矩阵和路径追踪矩阵
        
        Args:
            adj_matrix (np.ndarray): 邻接矩阵
            
        Returns:
            Tuple[np.ndarray, np.ndarray]: (最短距离矩阵, 路径追踪矩阵)
        """
        n = adj_matrix.shape[0]
        dist = adj_matrix.astype(float)
        dist[dist == 0] = np.inf
        np.fill_diagonal(dist, 0)
        
        next_node = np.full((n, n), -1)
        for i in range(n):
            for j in range(n):
                if adj_matrix[i][j] != 0:
                    next_node[i][j] = j
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        next_node[i][j] = next_node[i][k]
        
        return dist, next_node

    @staticmethod
    def reconstruct_path(next_node: np.ndarray, start: int, end: int) -> List[int]:
        """
        根据路径追踪矩阵重建最短路径
        
        Args:
            next_node (np.ndarray): 路径追踪矩阵
            start (int): 起始节点索引
            end (int): 目标节点索引
            
        Returns:
            List[int]: 最短路径节点索引列表
        """
        if next_node[start][end] == -1:
            return []
            
        path = [start]
        while start != end:
            start = next_node[start][end]
            path.append(start)
        return path
